package com.darrenchan.leetcode;

import java.util.*;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-03-31 15:02
 */
public class QLint104 {
    //小顶堆的解法
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null) {
            return null;
        }

        Queue<ListNode> queue = new PriorityQueue<>((o1, o2) -> (o1.val - o2.val));
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                queue.add(lists.get(i));
            }
        }

        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;
        while (!queue.isEmpty()) {
            ListNode poll = queue.poll();
            node.next = poll;
            node = node.next;
            if (poll.next != null) {
                queue.add(poll.next);
            }
        }

        return dummy.next;
    }

    //自底而上的解法
    public ListNode mergeKLists2(List<ListNode> lists) {
        if (lists == null) {
            return null;
        }

        while (lists.size() > 1) {
            List<ListNode> newLists = new ArrayList<>();
            for (int i = 0; i < lists.size(); i += 2) {
                ListNode node = null;
                if (i + 1 < lists.size()) {
                    node = mergeLists(lists.get(i), lists.get(i + 1));
                } else {
                    node = lists.get(i);
                }
                newLists.add(node);
            }
            lists = new ArrayList<>(newLists);
        }

        return lists.get(0);
    }

    private ListNode mergeLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }

        if (l1 != null) {
            node.next = l1;
        }

        if (l2 != null) {
            node.next = l2;
        }

        return dummy.next;
    }


    //自顶而下的解法
    public ListNode mergeKLists3(List<ListNode> lists) {
        if(lists == null) {
            return null;
        }

        return sortList(lists, 0, lists.size() - 1);
    }

    private ListNode sortList(List<ListNode> lists, int start, int end) {
        if(start == end) {
            return lists.get(start);
        }

        int mid = start + (end - start) / 2;
        ListNode left = sortList(lists, start, mid);
        ListNode right = sortList(lists, mid + 1, end);

        return mergeLists(left, right);
    }

}